package offer.day32;

public class No53GetNumberOfK {
    /*
     * 面试题53:在排序数组中查找数字
     * 题目一：数字在排序数组中出现的次数
     * 统计一个数字在排序数组中出现的次数。
     * 例如：输入排序数组{1，2，3，3，3，3，4，5}和数字3，
     * 由于3在这个数组中出现4次，因此输出4
     *
     * 二分查找/折半查找      https://www.cnblogs.com/yedushusheng/p/5524166.html
     *
     * 思路：  时间复杂度O(logn)  空间复杂度O(1)
     * 因为查找的是有序表，左移确定重复出现的第一个k和最后一个k的位置，然后就能够得到出现次数了
     *使用二分查找法的思想进行查找
     * 在数组中找到第一个k：
     * 二分查找中就是在与中间位置进行比较，所以首先计算中间索引值，然后得到数组的中间值，
     * 判断与k的关系：  若等于，看其是否为第一个k，是的情况：（两种情况：根据前一个元素是否存在区分，一种是没有前一个元素，则索引为0；一种是有前一个元素，索引大于0，且前一个值不等于k），则返回中间值即可
     * 										 否的情况，则将结束节点赋值为中间的前一位
     * 				若小于，则将起始位赋值为中间位置的后一位
     * 				若大于，则将结束位赋值为中间位置的前一位
     * 然后接着判断被分割后的部分是怎样的情况（也就是与k的关系，直到找到第一个k为止）
     *
     * 在数组中找到最后一个k：同找第一个k类似
     *
     *
     * */
    public static void main(String[] args) {
        No53GetNumberOfK g = new No53GetNumberOfK();
        int[] array = {1,2,3,3,3,3,3,4,5};
        int k = 3;
        System.out.println("数组中"+k+"出现了"+g.GetNumberOfK(array,k)+"次！！！");
    }

    private int GetNumberOfK(int[] array, int k) {
        int number=0;
        if(array!=null&&array.length!=0){
            int first=GetFirstNumberOfK(array,k,0,array.length-1);
            int last=GetLastNumberOfK(array,k,0,array.length-1);
            if(first>-1&&last>-1){
                number=last-first+1;
            }
        }
        return number;
    }

    private int GetLastNumberOfK(int[] array,int k,int start,int end){
        if(start>end){
            return -1;
        }
        int midIndex=(start+end)/2;
        int midData=array[midIndex];

        if(midData==k){
            if((midIndex+1<array.length&&array[midIndex+1]!=k) || midIndex==array.length-1){
                return midIndex;
            }else {
                start=midIndex+1;
            }
        }else if(midData>k){
            end=midIndex-1;
        }else{
            start=midIndex+1;
        }
        return GetLastNumberOfK(array,k,start,end);
    }

    private int GetFirstNumberOfK(int[] array,int k,int start,int end){
        if(start>end){
            return -1;
        }
        int midIndex=(start+end)/2;
        int midData=array[midIndex];

        if(midData==k){
            if((midIndex-1>=0&&array[midIndex-1]!=k) || midIndex==0){
                return midIndex;
            }else {
                end=midIndex-1;
            }
        }else if(midData>k){
            end=midIndex-1;
        }else{
            start=midIndex+1;
        }
        return GetFirstNumberOfK(array,k,start,end);
    }
}
